1. Field of the Invention
The present invention relates to the ciphering of digital data by means of algorithms intended to mask the original data to make them undetectable by a possible hacker. The present invention more specifically relates to an algorithm known as Rijndael implementing a same transformation on different portions of data to be ciphered, and among these, the AES algorithm (Advanced Encryption Standard, FIPS PUB 197) where the size of the data blocks is set to 128 bits.
Such an algorithm is generally executed by integrated circuits either by means of state machines in wired logic, or by means of microprocessors executing a program in the memory (generally, a ROM). The algorithm uses secret keys specific to integrated circuits or to the user, which are exploited by the algorithm to cipher the data. More specifically, the AES algorithm applies, to a data word or code divided into blocks, a same transformation several times in a row based on different ciphering sub-keys (more specifically on portions of a binary word forming a key). An example of application of the present invention is the use of such an algorithm in electronic elements of smart card type.
2. Discussion of the Related Art
FIG. 1 illustrates, in a simplified timing diagram, the main steps of an AES-type algorithm. Only the ciphering will be described, the deciphering using the inverse transformations. For more details, reference may be made to work “The Design of Rijndael” by Joan Daemen and Vincent Rijmen, published by Springer-Veriag (ISBN 3-540-42580-2) and to the AES standard (FIPS PUB 197).
This algorithm ciphers a word or code S0 of a predetermined number of bits (128 bits for the AES) into another word or code Sn of the same size. The data to be processed are actually formed of several words or codes resulting from a previous division of the data into words all having the same size. The ciphering and the deciphering rest on a secret key having a length (128, 192, or 256 bits for the AES) which conditions the ciphering security.
In practice, each step of an AES-type algorithm processes a matrix of four lines and four columns, representing a word, and each element of which is a byte or block of the processed 128-bit code. To simplify the following description, reference will be made, for each step, to a state considered as being a matrix.
The invention will be described in relation with an AES-type algorithm applied to 32-bit words divided into bytes, which corresponds to the most frequent case.
To implement the ciphering or deciphering algorithm, it is started by generating, based on the secret key over 128, 192, or 256 bits, respectively 11, 13, or 15 sub-keys, each also comprising 128 bits. The sub-keys are intended to be used by the algorithm as will be described in relation with FIG. 1.
It is started from an initial state (block 1, STATE INIT) S of the data code or word to be ciphered.
A first phase of the ciphering method is an operation (block 2, ADDROUNDKEY) which comprises performing an XOR-type combination of initial state S with first sub-key K0. A first intermediary state S1 is obtained.
A second phase of the ciphering method comprises performing several rounds or cycles of a same transformation T involving, at each round, the state Si-1 obtained at the preceding round and a current sub-key Ki. The number of rounds of transformation T corresponds to n−1, that is, to number n+1 of derived sub-keys, minus 2.
Each round transformation T is formed of four successively-applied operations.
FIG. 2 illustrates in further detail these four operations on a matrix 20 of four lines and four columns of bytes to which an AES-type algorithm applies.
A first operation (block 3, SHIFTROWS) comprises performing a rotation on the last three lines of matrix 20. First line 201 of matrix 20 remains unchanged. Second line 202 undergoes a rotation by one byte. Third line 203 undergoes a rotation by two bytes. Fourth line 204 undergoes a rotation by three bytes.
A second operation (block 4, SUBBYTES) of round transformation T is a non-linear transformation in which each byte of matrix 20′ forming the current state is replaced by its image, generally taken from a precalculated substitution box (SBOX). As illustrated in FIG. 2, substitution box SBOX can be obtained by two combined transformations. A first transformation (block 41, INV) comprises inverting the considered byte (the element of matrix 20′) in the finite field of order 28 (to correspond to the byte), byte 00 forming its own image. This inversion is followed by an affine transformation (block 42, AFFINE).
The first and second operations may be inverted.
A third operation (block 5, MIXCOLUMNS) of round transformation T comprises considering each column of matrix 20″ resulting from the previous step as a polynomial on the finite field of order 28, and multiplying each of these polynomials by a combination polynomial P[X] modulo a polynomial M[X].
A fourth and last operation (block 6, ADDROUNDKEY) of round transformation T of rank i comprises applying sub-key Ki to the resulting matrix 20″ of the preceding state to obtain a matrix 20′″ in which each byte of matrix 20″ has been combined by XOR, bit-to-bit, with a byte Ki(j,l)—with j ranging between 0 and 3 (rank of the line in the matrix) and l ranging between 0 and 3 (rank of the column in the matrix)—of sub-key Ki. This operation 6 is the same as operation 2 of the first ciphering phase, but performed with a different sub-key.
At the end of operation 6, for a round of rank i, a state Si=T(Ki, Si-1) is obtained. The four operations of the round transformation are repeated n−1 times, that is, after operation 6, it is returned to operation 3 to perform a new round with a next sub-key.
The third phase of the AES ciphering algorithm (FIG. 1) comprises a last round slightly modified with respect to that illustrated in FIG. 2. In fact, operations of the round transformation are reproduced except for the third one (MIXCOLUMNS). In FIG. 1, this last round has been illustrated by blocks 7, 8, and 9 resuming the previously-described operations of blocks 3, 4, and 6 with, as a key for operation 9, last sub-key Kn.
State Sn=T′(Kn, Sn-1) is then obtained. This result may be shaped up (block 10, RESULT FORM) for subsequent use.
The critical part in terms of storage of an AES-type algorithm lies in the execution of step SUBBYTE (blocks 4 and 8) using a substitution box. This table generally represents a 256-byte matrix that must be pre-calculated, then read from a storage memory 16 times on each round of the AES algorithm.
Another possible solution comprises storing a table with the results of substitution box SBOX and of the column transformation (MIXCOLUMNS). The stored table and the results of the two transformations are applied to a byte of each state. A disadvantage is that the size of this table is then equal to 210 bytes.
Another problem of known AES-type algorithms is linked to their sensitivity to attacks by analysis of the current consumption of the circuit executing the algorithm. Such an attack known as a DPA (Differential Power Analysis) comprises correlating the consumption of the integrated circuit executing the algorithm with calculation results involving the secret keys used on ciphering or deciphering. In practice, from a message to be ciphered and assumptions as to the secret key, a curve of statistic time correlation between the consumption of the product for the message ciphering and an intermediary value calculated by the circuit is established. Such consumption attacks are described in literature (see, for instance, article “Differential Power Analysis” by Paul Kocher, Joshua Jaffe, and Benjamin Jun, published in 1999, CRYPTO 99 conference, pages 388 to 397, Springer-Verlag LNCS 1666).
Examples of circuits implementing or using the AES algorithm to cipher/decipher data are described in documents US-A-2003/0133568, US-A-2003/0068036, and US-A-2003/0099352.
According to a first aspect, the present invention aims at providing a novel architecture of a circuit for executing an algorithm of AES-type, or more generally of Rijndael type, which is less bulky than conventional architectures.
The invention also aims at providing an architecture enabling execution of all the rounds of the algorithm by means of a same group of hardware operators.
The invention also aims at reducing the memory size necessary for storing the tables.
The invention also aims at providing a solution which is compatible with the execution of the AES-type algorithm by a state machine in wired logic in an integrated circuit.
According to a second aspect, the present invention provides introducing at least one random value into the execution of the AES-type algorithm to make it resistant against attacks of differential power analysis type.